You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
- For example, the root-to-leaf path
1 -> 2 -> 3represents the number123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
Example 1:
Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path1->2represents the number12. The root-to-leaf path1->3represents the number13. Therefore, sum = 12 + 13 =25.
Example 2:
Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path4->9->5represents the number 495. The root-to-leaf path4->9->1represents the number 491. The root-to-leaf path4->0represents the number 40. Therefore, sum = 495 + 491 + 40 =1026.
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. 0 <= Node.val <= 9- The depth of the tree will not exceed
10.
Average Rating: 4.57 (28 votes)
Solution
Overview
Prerequisites
There are three DFS ways to traverse the tree: preorder, postorder and inorder. Please check two minutes picture explanation, if you don't remember them quite well: here is Python version and here is Java version.
Optimal Strategy to Solve the Problem
Root-to-left traversal is so-called DFS preorder traversal. To implement it, one has to follow straightforward strategy Root->Left->Right.
Since one has to visit all nodes, the best possible time complexity here is linear. Hence all interest here is to improve the space complexity.
There are 3 ways to implement preorder traversal: iterative, recursive and Morris.
Iterative and recursive approaches here do the job in one pass, but they both need up to O(H) space to keep the stack, where H is a tree height.
Morris approach is two-pass approach, but it's a constant-space one.
Approach 1: Iterative Preorder Traversal.
Intuition
Here we implement standard iterative preorder traversal with the stack:
-
Push root into stack.
-
While stack is not empty:
-
Pop out a node from stack and update the current number.
-
If the node is a leaf, update root-to-leaf sum.
-
Push right and left child nodes into stack.
-
-
Return root-to-leaf sum.
Implementation
Note, that Javadocs recommends to use ArrayDeque, and not Stack as a stack implementation.
Complexity Analysis
-
Time complexity: O(N) since one has to visit each node.
-
Space complexity: up to O(H) to keep the stack, where H is a tree height.
Approach 2: Recursive Preorder Traversal.
Iterative approach 1 could be converted into recursive one.
Recursive preorder traversal is extremely simple: follow Root->Left->Right direction, i.e. do all the business with the node (= update the current number and root-to-leaf sum), and then do the recursive calls for the left and right child nodes.
P.S.
Here is the difference between preorder and the other DFS recursive traversals.
On the following figure the nodes are numerated in the order you visit them,
please follow 1-2-3-4-5 to compare different DFS strategies implemented as
recursion.
Implementation
Complexity Analysis
-
Time complexity: O(N) since one has to visit each node.
-
Space complexity: up to O(H) to keep the recursion stack, where H is a tree height.
Approach 3: Morris Preorder Traversal.
We discussed already iterative and recursive preorder traversals, which both have great time complexity though use up to O(H) to keep the stack. We could trade in performance to save space.
The idea of Morris preorder traversal is simple: to use no space but to traverse the tree.
How that could be even possible? At each node one has to decide where to go: to the left or tj the right, traverse the left subtree or traverse the right subtree. How one could know that the left subtree is already done if no additional memory is allowed?
The idea of Morris
algorithm is to set the temporary link between the node and its
predecessor:
predecessor.right = root.
So one starts from the node, computes its predecessor and
verifies if the link is present.
-
There is no link? Set it and go to the left subtree.
-
There is a link? Break it and go to the right subtree.
There is one small issue to deal with : what if there is no left child, i.e. there is no left subtree? Then go straightforward to the right subtree.
Implementation
Complexity Analysis
-
Time complexity: O(N).
-
Space complexity: O(1).
June 26, 2020 7:33 AM
do we suppose to know 'Morris' in the interview too?
No global variable.
public int sumNumbers(TreeNode root) {
return sumNumbers(root, 0);
}
int sumNumbers(TreeNode root, int sum) {
if (root == null) return 0;
sum = sum*10 + root.val;
if (root.left == null && root.right == null)
return sum;
return sumNumbers(root.left, sum) + sumNumbers(root.right, sum);
}June 27, 2020 7:22 AM
Morris approach is two-pass approach, but it's a constant-space one.
If I understand this correctly, this two-pass means we go through the right branch twice:
- 1st time to build the connection
predecessor.right = root - 2nd time to
visitthe while traversing
Essentially, it is to trade off the first pass and use the rightLeaf.right pointer as a link to replace backtracking / popping stack so that we can get back to the previous stackframe / position without extra space:
the rightLeaf.right pointer has been allocated, then the only extra space we need is just the 2 extra pointers: root and predecessor.
April 4, 2020 7:12 AM
Morris Algo is too Good
here is my straighforward level order solution -- just traverse the tree in level order fashon and update the sum at each crossed node in a given root to leaf path
def sumNumbers(self, root: TreeNode) -> int:
if root is None:
return 0
q = deque()
q.append((root, root.val))
total = 0
while q:
node, path_sum = q.popleft()
print(path_sum)
if node.left is None and node.right is None:
total += path_sum
if node.left is not None:
q.append((node.left, path_sum*10+node.left.val))
if node.right is not None:
q.append((node.right, path_sum*10+node.right.val))
return total
Morris Algorithm is a great approach. But don't you think it is too hard to code without any bug at the actual interview? Should I code this algorithm? Or is it ok to just mention about it?
Backtracking solution:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sumNumbers(self, root: TreeNode) -> int:
ans = 0
total = 0
def dfs(node=root):
nonlocal ans, total
if not node:
return
total = total * 10 + node.val
if not node.left and not node.right:
ans += total
else:
dfs(node.left)
dfs(node.right)
total = (total - node.val) // 10
dfs()
return ans
March 17, 2020 10:43 AM
wow Morris algorithm is truly amazing!
Iterative: best time.
Morris: constant space.
Recursive: simple to write.
I know this but never gave a thought on this. Thanks for above points.
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/26/2020 12:53 | Accepted | 4 ms | 12.7 MB | cpp |
x
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: int sumNumbers(TreeNode* root) { }};
